翻訳と辞書 Words near each other ・ (S)-Ipsdienol ・ (S)-limonene 3-monooxygenase ・ (S)-limonene 6-monooxygenase ・ (S)-limonene 7-monooxygenase ・ (S)-mandelate dehydrogenase ・ (S)-methylmalonyl-CoA hydrolase ・ (S)-N-acetyl-1-phenylethylamine hydrolase ・ (S)-norcoclaurine synthase ・ (S)-scoulerine 9-O-methyltransferase ・ (S)-squalene-2,3-epoxide hydro-lyase ・ (S)-stylopine synthase ・ (S)-sulfolactate dehydrogenase ・ (S)-tetrahydroprotoberberine N-methyltransferase ・ (S)-usnate reductase ・ (S,S)-butanediol dehydrogenase ・ (SAT, ε-UNSAT) ・ (SCENE) Metrospace ・ (See Inside) ・ (Set This) World Ablaze ・ (Sex) Appeal ・ (Shake That) Cosmic Thing ・ (Shake, Shake, Shake) Shake Your Booty ・ (She Was A) Hotel Detective ・ (She's So) Selfish ・ (She's) Sexy + 17 ・ (sic)nesses ・ (Sittin' On) The Dock of the Bay ・ (Skp1-protein)-hydroxyproline N-acetylglucosaminyltransferase ・ (So Tired of Standing Still We Got to) Move On ・ (Something Inside) So Strong Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク (SAT, ε-UNSAT) ： ウィキペディア英語版 (SAT, ε-UNSAT) In computational complexity theory, (SAT, ε-UNSAT) is a language that is used in the proof of the PCP theorem, which relates the language NP to probabilistically checkable proof systems. For a given 3-CNF formula, Φ, and a constant, ε < 1, Φ is in (SAT, ε-UNSAT) if it is satisfiable and not in (SAT, ε-UNSAT) if the maximum number of satisfiable clauses (MAX-3SAT) is less than or equal to (1-ε) times the number of clauses in Φ. If neither of these conditions are true, the membership of Φ in (SAT, ε-UNSAT) is undefined. == Complexity == It can be shown that (SAT, ε-UNSAT) characterizes PCP(O(log n), O(1)). $L\; \backslash in\; \backslash mbox(O(\backslash log\; n),O(1))$, then $L\; \backslash le\; (\; \backslash mbox,\; \backslash epsilon-\backslash mbox)$. (See PCP theorem for more information) Let each bit in the proof ''y'' be $y\_1,\; y\_2,\; \backslash ldots,\; y\_m$. First, it is necessary to encode when the verifier accepts in 3CNF clauses $\backslash phi=\backslash bigwedge\_r\; \backslash phi\_r$. Next, for each random string ''r'', construct a sub-formula $\backslash phi\_r$. For a fixed ''r'', its possible to determine all the variables queried, Enumerate each random string ''r'', and add a clause $\backslash phi\_r\; =\; f\_r\; (y\_,\; y\_,\; \backslash ldots\; ,\; y\_)\; \backslash$, where $f\_r$ is true if and only if the PCP system accepts on reading the given random bits ''r''. There are at most $2^q$ SAT clauses. After these clauses are converted into 3CNF clauses, there are at most $q\; 2\; ^\; q$ clauses. If $x\; \backslash in\; L$, then there is a proof ''y'' such that is accepted for every random string ''r''. Therefore $\backslash phi(y\_1,y\_2,\backslash ldots,y\_m)$ is satisfiable. If $x\; \backslash notin\; L$, then for every assignment to $y\_1,\; y\_2,\; \backslash ldots,\; y\_m$ the corresponding proof causes the verifier to reject for half of the random strings ''r''. For each ''r'' that is rejected one of the clauses in $f\_r$ fails. Therefore at least $\backslash epsilon\; =\; \backslash frac$ fraction of the clauses fail. Therefore $L\; \backslash le\; (\backslash mbox,\; \backslash epsilon-\backslash mbox)$. For $(SAT,\; \backslash epsilon-UNSAT)\; \backslash in\; PCP(O(\backslash log\; n),\; O(1))$, let the proof that the PCP system reads be a satisfying assignment for the input 3-CNF, Φ. The system chooses $O(1/\backslash epsilon)$ clauses of the proof to check if they are truly satisfied. Note that only $\backslash log\; n$ random bits are needed to choose one of $n$ clauses, and thus only $O(\backslash log\; n/\backslash epsilon)\; =\; O(\backslash log\; n)$ total random bits are needed. (Remember that ε is a constant.) For each clause to be checked, only 3 bits need to be read, and thus only $O(3/\backslash epsilon)\; =\; O(1)$ (a constant number) of bits from the proof need to be read. The system rejects if any of the clauses are not satisfied. If Φ is satisfiable, then there exists a proof (a truly satisfying assignment) that the system will always accept. If Φ is not in (SAT, ε-UNSAT), this means that an ε fraction of the clauses is not satisfiable. The probability that this system will accept in this case is . Therefore, $(SAT,\; \backslash epsilon-UNSAT)\; \backslash in\; PCP(O(\backslash log\; n),\; O(1))$. (SAT, ε-UNSAT) is an NP-hard language. As part of the proof of the PCP theorem, (SAT, ε-UNSAT) has also been shown to be in PCP(O(log n), O(1)). 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「(SAT, ε-UNSAT)」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.